package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 二叉树的层平均值
 * Created by Administrator on 2020/1/12.
 */
public class AverageOfLevels {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double>result = new ArrayList<>();
        if (root == null){
            return result;
        }
        List<Map<String, Long>>lists = new ArrayList<>();
        averageOfLevels(root, lists, 0);
        return lists.stream().map(s -> s.get("sum").doubleValue()/s.get("total").doubleValue()).collect(Collectors.toList());
    }

    public void averageOfLevels(TreeNode root, List<Map<String, Long>>lists, int level) {
        if(root != null){
            if(lists.size() == level || lists.get(level) == null){
                Map<String,Long>map = new HashMap<>();
                map.put("total", 1L);
                map.put("sum", Long.valueOf(root.val));
                lists.add(map);
            }else{
                Map<String,Long>map= lists.get(level);
                map.compute("total", (k,v)-> v+1);
                map.compute("sum", (k,v)-> v+root.val);
            }
            if(root.left != null){
                averageOfLevels(root.left, lists, level+1);
            }

            if(root.right != null){
                averageOfLevels(root.right, lists, level+1);
            }
        }
    }

//    public List<Double> averageOfLevels(TreeNode root) {
//        List<Double>result = new ArrayList<>();
//        if (root == null){
//            return result;
//        }
//        List<List<Long>>lists = new ArrayList<>();
//        averageOfLevels(root, lists, 0);
//        return lists.stream().map(s -> s.stream().reduce(0L, (v1,v2)->v1+v2).doubleValue()/s.size()).collect(Collectors.toList());
//    }
//
//    public void averageOfLevels(TreeNode root, List<List<Long>>lists, int level) {
//        if(root != null){
//            if(lists.size() == level || lists.get(level) == null){
//                List<Long> l= new ArrayList<>();
//                l.add(Long.valueOf(root.val));
//                lists.add(l);
//            }else{
//                lists.get(level).add(Long.valueOf(root.val));
//            }
//            if(root.left != null){
//                averageOfLevels(root.left, lists, level+1);
//            }
//
//            if(root.right != null){
//                averageOfLevels(root.right, lists, level+1);
//            }
//        }
//    }
}
